/**
 * 项目名称: Topic_105.cpp
 * 项目路径: study/DataStructure/LeetCode/树/简单
 * 编辑时间: 2024年08月15日15时41分23秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    unordered_map<int,int>map;
    /**
     * 算法思想:不断递归缩小前序,中序子树范围
     * 前序遍历 = 跟结点 [左子树结点] [右子树结点]
     * 中序遍历 = [左子树结点] 根节点 [右子树结点]
     * 根节点 + [左子树结点] = [左子树结点] + 根节点
     * @param preorder
     * @param inorder
     * @param pl
     * @param pr
     * @param il
     * @param ir
     * @return
     */
    TreeNode* build(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir){
        if(pl>pr)return nullptr;

        TreeNode* root = new TreeNode;
        root->val = preorder[pl];

        int mid = map[root->val];

        //递归遍历左子树
        root->left = build(preorder,inorder,pl+1,pl+1+mid-1-il,il,mid-1);
        //递归遍历右子树
        root->right = build(preorder,inorder,pl+1+mid-1-il+1,pr,mid+1,ir);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty())return nullptr;
        for(int i = 0 ;i<inorder.size();i++)map[inorder[i]]=i;
        return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};
